#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;

void swap (int &a, int &b)
{
    int tmp = a;
    a = b;
    b = tmp;
}

class Solution {
    public:
        void nextPermutation(vector<int> &num) {
           if (num.size() <= 1) return; 
           int last = num.size()-1;
           while (last > 0 && num[last-1] >= num[last]){ 
               //cout << last << " ";
               last--; 
           }
           if (last == 0) {reverse(num.begin(), num.end()); return;}
           int j = num.size() -1;
           while (num[j] <= num[last-1]) j--;
           swap(num[j], num[last-1]);
           cout << "Last" << " " << last << endl;
           reverse(num.begin()+last, num.end());
        }
};

int main(int argc, char **argv)
{
    Solution mySolution;
    cout << "-----------------Test 1--------------------" << endl;
    vector<int> num;
    num.push_back(1);
    num.push_back(3);
    num.push_back(2);
    mySolution.nextPermutation(num);
    for (int i = 0; i < 3; i++)
        cout << num[i] << " ";
    cout << endl;
    cout << "-----------------Test 2--------------------" << endl;
    vector<int> num1;
    num1.push_back(5);
    num1.push_back(1);
    num1.push_back(1);
    mySolution.nextPermutation(num1);
    for (int i = 0; i < 3; i++)
        cout << num1[i] << " ";
    cout << endl;


    cout << "-----------------Test 3--------------------" << endl;
    vector<int> num3;
    num3.push_back(1);
    num3.push_back(5);
    num3.push_back(1);
    mySolution.nextPermutation(num3);
    for (int i = 0; i < 3; i++)
        cout << num3[i] << " ";
    cout << endl;


    cout << "-----------------Test 4--------------------" << endl;


    cout << "-----------------Test 5--------------------" << endl;



}
